// 字符串有三种编辑操作:插入一个字符、删除一个字符或者替换一个字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

//  

// 示例 1:

// 输入: 
// first = "pale"
// second = "ple"
// 输出: True
//  

// 示例 2:

// 输入: 
// first = "pales"
// second = "pal"
// 输出: False

#include "stdc++.h"

/* 双指针 + 编辑距离
分别从两个字符串的两边向中间匹配，一旦不一样就停止，
这时剩下的first[i,j]和second[i,k]
如果长度均小于等于1（注意临界条件）则结果为True，否则False。
*/
class Solution {
public:
    bool oneEditAway(string first, string second) {
        if (first == second) {
            return true;
        }
        int m = first.size();
        int n = second.size();
        if (abs(m - n) > 1) {
            return false;
        }
        int i = 0; // 左指针
        int j = m-1; // first右指针
        int k = n-1; // second右指针
        while(i < m && i < n && first[i] == second[i]) {
            ++i;
        }
        while(j >= 0 && k >= 0 && first[j] == second[k]) {
            --j;
            --k;
        }
        return j - i < 1 && k - i < 1;
    }
};

class Solution {
public:
    bool oneEditAway(string first, string second) {
        int m = first.size();
        int n = second.size();
        if (n - m == 1) {
            return oneInsert(first, second);
        } else if (m - n == 1) {
            return oneInsert(second, first);
        } else if (m == n) {
            bool foundDiff = false;
            for (int i = 0; i < m; ++i) {
                if (first[i] != second[i]) {
                    if (foundDiff) {
                        return false;
                    }
                    foundDiff = true;
                }
            }
            return true;
        }
        return false;
    }
private:
    bool oneInsert(string shorter, string longer) {
        int length1 = shorter.size(), length2 = longer.size();
        int index1 = 0, index2 = 0;
        while (index1 < length1 && index2 < length2) {
            if (shorter[index1] == longer[index2]) {
                index1++;
            }
            index2++;
            if (index2 - index1 > 1) {
                return false;
            }
        }
        return true;
    }
};
